package BinaryTree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        private char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node4.right = node5;
        node3.left = node6;

        return node1;
    }

    public void preOrder1(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder1(root.left);
        preOrder1(root.right);

    }

    List<Character> ret = new ArrayList<>();
    public List<Character> preOrder2(TreeNode root){
        if (root == null){
            return ret;
        }

        ret.add(root.val);
        preOrder2(root.left);
        preOrder2(root.right);
        return ret;
    }

    public List<Character> preOrder(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if (root == null){
            return ret;
        }

        ret.add(root.val);
        List<Character> leftTree = preOrder(root.left);
        ret.addAll(leftTree);

        List<Character> rightTree = preOrder(root.right);
        ret.addAll(rightTree);

        return ret;
    }

    public void inOrder1(TreeNode root){
        if (root == null){
            return;
        }

        inOrder1(root.left);
        System.out.print(root.val + " ");
        inOrder1(root.right);

    }

    List<Character> ret1 = new ArrayList<>();
    public List<Character> inOrder2(TreeNode root){
        if (root == null){
            return null;
        }

        inOrder2(root.left);
        ret1.add(root.val);
        inOrder2(root.right);
        return ret1;
    }

    public List<Character> inOrder(TreeNode root){
        List<Character> ret = new ArrayList<>();

        if (root == null){
            return ret;
        }

        List<Character> leftTree = inOrder(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);

        List<Character> rightTree = inOrder(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        System.out.println(binaryTree.inOrder(root));
    }
}
